package com.zzz.offer.binaryTree;


import java.util.Arrays;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class BinaryTree {

    public static void main(String[] args) {

    }

    public TreeNode reConstructBinaryTree(int[] pre, int[] vin) {

        if (pre.length == 0) {
            return null;
        }

        TreeNode node = new TreeNode(pre[0]);

        int leftChildCount = 0;

        // 将左节点的个数算出来，就能知道左节点的 前序数组范围  和 左节点 中序数组范围，
        // 并能推算出右节点的前序范围，和右节点的中序范围
        // 因为前序和中序遍历  左孩子节点 的范围都在一起
        // 中序 1 [2, 4, 7] [3, 5, 6, 8]
        // 前序 [4, 7, 2] 1 [5, 3, 8, 6]
        // 按这个规律 分三步
        // 1. 把头结点找出来   中序的第一个元素
        // 2. 把左孩子个数找出来，遍历前序，直到等于头结点，就能知道左孩子个数 3
        // 3. 通过左孩子个数 3, 把中序的左孩子 范围找出来  [1, 3]  右孩子范围找出来 [4, 7]
        // 4. 通过左孩子个数 3, 把前序的左孩子 范围找出来  [0, 2]  右孩子范围找出来 [4, 7]
        // 5. 把中序的左孩子 和 前序的左孩子  就可以当做 左子树的中序和前序 放入递归中   如果左孩子范围为空，那么就不需要进入递归
        //    返回 值 是左子树的头结点，直接赋值给当前节点的左孩子
        // 5. 把中序的右孩子 和 前序的右孩子  就可以当做 右子树的中序和前序 放入递归中   如果右孩子范围为空，那么就不需要进入递归
        //    返回 值 是右子树的头结点，直接赋值给当前节点的右孩子
        // 6. 返回当前的主节点
        for (int i = 0; i < vin.length; i++) {
            if (vin[i] == pre[0]) {
                break;
            }
            leftChildCount++;
        }


        int[] leftChildPre = Arrays.copyOfRange(pre, 1, leftChildCount + 1);
        int[] leftChildVin = Arrays.copyOfRange(vin, 0, leftChildCount);
        if (leftChildPre.length > 0)
            node.left = reConstructBinaryTree(leftChildPre, leftChildVin);


        int[] rightChildPre = Arrays.copyOfRange(pre, leftChildCount + 1, pre.length);
        int[] rightChildVin = Arrays.copyOfRange(vin, leftChildCount + 1, vin.length);
        if (rightChildPre.length > 0)
            node.right = reConstructBinaryTree(rightChildPre, rightChildVin);

        return node;
    }


}
